/**
 * @author yuanwanli
 * @des   利用递归算法，使用二分查找，找到小于等于 t的最后一个数
 * @date 2020/8/4
 */
fun main() {
    val array = arrayOf(-4, 1, 2, 2, 5, 5, 5, 8, 10)
//    val array = arrayOf(5, 5, 5, 5, 5, 5, 5, 5, 5)
    val binarySearch = binarySearch(array, 0, array.size - 1, 6)
    println(binarySearch)
}
fun binarySearch(array: Array<Int>, low:Int,high: Int, value: Int) :Int{
    var middle=low+((high-low)shr 1)
    println("low=="+low+"hight=="+high+"middle=="+middle)
    return if (array[middle]<=value){
        if (middle==high||array[middle+1]>value){
            middle
        }else{
            binarySearch(array,middle+1,high,value)
        }
    }else{
        binarySearch(array,low,middle-1,value)
    }
}